/**
 * 
 */
package sorting;

import utils.HelpUtils;
import utils.PrintUtils;

/**
 * @author Michael
*Given  an integer array and a specific integer x, write a program to do a three-partition.
 That is, the left part of the array is less than x, the middle part is equal to x and
 the right part is bigger than x
 E.g     array: 0 1 2 1 2 1 2 0 0 2 1 0 0 2 2 1 0  ==>  0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 
 
 http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
 */
public class DutchFlagProblem {
	
	public static int[] sort(int[] a, int middle) {
		if (a == null || a.length == 0)
			return a;
		
		int low = 0;
		int high = a.length - 1;
		int read = 0;
		while (read <= high) {
			if (a[read] < middle) {
				HelpUtils.swap(a, read++, low++);
			}
			else if (a[read] > middle) {
				HelpUtils.swap(a, read, high--);
			}
			else {
				read++;
			}
		}
		
		return a;
	}
	

	public static int[] duchFlagSort(int[] arr) {
		if (arr == null || arr.length == 0)
			return arr;
		
		int low = 0;
		int mid = 0;
		int high = arr.length - 1;
		while (mid <= high) {
			if (arr[mid] == 0) {
				HelpUtils.swap(arr, mid++, low++);				
			}
			else if (arr[mid] == 1) {
				mid++;
			}
			else { // arr[mid] == 2;
				HelpUtils.swap(arr, mid, high--);
			}
		}
		
		return arr;
	}
	
	/**
	 * 
	 */
	public DutchFlagProblem() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 0, 1, 2, 1, 2, 1, 2, 0, 0, 2, 1, 0, 0, 2, 2, 1, 0 };
		PrintUtils.printArray(a);
		PrintUtils.printArray(sort(a, 1));
		a = new int[] { 0, 1, 0, 0, 1, 0, 0, 1, 0 };
		PrintUtils.printArray(duchFlagSort(a));

	}

}
